package com.south.base.test.arithmetic;

import java.util.Arrays;

/**
 * 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
 *
 * @author Administrator
 * @date 2019/5/28 11:09
 */
public class PartitionArrToDouble {
    /**
     * 用时63ms
     *
     * @param nums
     * @return
     */
    public static boolean canPartition(int[] nums) {
        //动态规划，背包问题，从nums中选择一部分数字组合，填满容量为sum/2的背包
        int n = nums.length;
        if (n == 0) {
            return false;
        }

        //确定背包c的大小
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        //两个相等的整数的和一定为偶数
        if (sum % 2 == 1) {
            return false;
        }

        int c = sum / 2;
        //动态规划
        //明确状态：dp[m][n] 考虑是否将第m个数字放入容量为n的背包
        boolean[][] dp = new boolean[n][c + 1];

        //状态初始化
        for (int i = 0; i <= c; i++) {
            dp[0][i] = i == nums[0];
        }

        //状态转移方程：dp[m][n] = dp[m-1][n] || dp[m-1][n-nums[m]]
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= c; j++) {
                dp[i][j] = dp[i - 1][j];
                if (nums[i] <= j) {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
                }

            }
        }

        return dp[n - 1][c];
    }

    /**
     * 用时3ms
     *
     * @param nums
     * @return
     */
    public static boolean canPartition2(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if ((sum % 2) == 1) {
            //如果和是奇数，直接返回false
            return false;
        }

        Arrays.sort(nums);
        if (nums[nums.length - 1] > sum / 2) {
            //如果最大的一个数超过了总和的一半，返回false
            return false;
        }
        sum = sum / 2;

        //现在只需要找数组中是否存在相加等于sum/2的子数组存在即可
        return hasChildrenArray(nums, sum, nums.length - 1);
    }

    private static boolean hasChildrenArray(int[] nums, int sum, int endIndex) {
        if (endIndex < 0) {
            return false;
        }
        if (nums[endIndex] == sum) {
            return true;
        } else if (nums[endIndex] < sum) {
            return hasChildrenArray(nums, sum - nums[endIndex], endIndex - 1) || hasChildrenArray(nums, sum, endIndex - 1);
        } else {
            return hasChildrenArray(nums, sum, endIndex - 1);
        }
    }

    public static void main(String[] args) {
        System.out.println(canPartition(new int[]{71, 70, 66, 54, 32, 63, 38, 98, 4, 22, 61, 40, 6, 8, 6, 21, 71, 36, 30, 34, 44, 60, 89, 53, 60, 56, 73, 14, 63, 37, 15, 58, 51, 88, 88, 32, 80, 32, 10, 89, 67, 29, 68, 65, 34, 15, 88, 8, 57, 78, 37, 63, 73, 65, 47, 39, 32, 74, 31, 44, 43, 4, 10, 8, 96, 22, 58, 87, 29, 99, 79, 13, 96, 21, 62, 71, 34, 55, 72, 3, 96, 7, 36, 64, 30, 6, 14, 87, 12, 90, 40, 13, 29, 21, 94, 33, 99, 86, 4, 100}));
    }
}
